public class Solution1289 {
    public int minFallingPathSum(int[][] grid) {
        int[][] f=new int[grid.length][grid[0].length];
        System.arraycopy(grid[0], 0, f[0], 0, grid[0].length);
        for (int i=1;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                f[i][j]=Integer.MAX_VALUE;
                for (int k=0;k<grid[0].length;k++){
                    if (j!=k){
                        f[i][j]=Math.min(f[i][j],f[i-1][k]+grid[i][j]);
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE;
        for (int i=0;i<grid[0].length;i++){
            ans=Math.min(ans,f[grid.length-1][i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1289().minFallingPathSum(new int[][]{{1,2,3},{4,5,6},{7,8,9}}));
    }
}
